package com.multimedia.scala.euler
/*
Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a  b, then a and b are an amicable pair and
each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110;
therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.
 */
object Asd21 {
    def main(args : Array[String]) : Unit = {
        var cache_yes = scala.collection.mutable.Set[Int]()//amicable digits
        var cache_no = scala.collection.mutable.Set[Int]()//not amicable digits
        def amicable(y: Int): Boolean = {
            def divisors(x: Int) = (1 to x/2).filter(x%_==0)

            if (cache_yes(y)) return true
            if (cache_no(y)) return false
            val pair = divisors(y).sum
            if (!cache_no(pair)&&pair!=y&&y==divisors(pair).sum) {
                cache_yes += y
                cache_yes += pair
                return true
            } else {
                cache_no += y
                return false
            }
        }
        val rez = (1 to 10000).filter(amicable)
        //rez.foreach(println)
        println(rez.sum)
    }
}
